1. Field of the Invention
The present invention relates to a method for dynamically allocate memories in an Ethernet switching architecture. More specifically this invention relates to an Ethernet switching architecture provided with an optimized single linked list for dynamically allocate a shared memory through a free-link RAM during the packet receiving & transmitting process, in order to achieve the object of improving the transmission bandwidth of network switching.
2. Description of the Related Art
A shared memory architecture is one that uses a single common memory as a switching device for network packets between the input ports and output ports. Through the path of data receiving of an input port, a received packet can be stored on the shared memory and can be assigned and transmitted to the path of data transmitting of an appropriate output port. And it is often used as a main structure for LAN (Local Area Network) switching because of the advantages of lowering cost, simplifying design requirements, and enabling easy implementation.
A shared memory may be divided into a plurality of contiguous data buffers that each has a fixed-length of 2k bytes and used as a FIFO device to store the received packets from a plurality of input ports and to transmit the received packets to an appropriate output port. This is simple for hardware configuration, however, the length of the received packet could be considerably smaller than the fixed length and the usage efficiency would dramatically reduced.
To solve this problem, a shared memory is often configured as a plurality blocks of discontiguous data buffers with a fixed length of 256 bytes to store the received packet segments from a plurality of input ports. After the plurality of packet segments have been received from the input ports, the shared memory would then assign the free data buffers to the plurality of packet segments. At the mean time, a link RAM mapping to the shared memory would store the corresponding link addresses and a linked list of the block addresses of the plurality of packet segments. According to the block addresses, the corresponding link addresses, and the designated output ports of the plurality of packet segments, the plurality of packet segments will be inserted to a corresponding output queue of an appropriate output port. Here, the output queue represents the stream of packets waiting in the path of data transmitting to be transmitted to a corresponding output port.
FIG. 1 is a diagram simplified illustrating a conventional Ethernet switching architecture. As shown in the diagram, a shared memory 10 is configured to have a plurality of blocking data buffers 11 with same size. The shared memory consists of a free-buffer pool 12 and a plurality of assigned buffers 13. The free-buffer pool 12 stores blank blocks to be assigned to the packet segments 21 waiting to be received, and those been released from the plurality of assigned buffers 13 after the packet segments have been read. And the plurality of assigned buffers 13 store packet segments received from the plurality of input ports 20. Additionally, the number of link address spaces 31 on a link RAM 30 is configured to be the same as the block counts on the shared memory 10. The link addresses 33 and the block addresses 14 of the shared memory 10 are in a mapping relation 15.
For instance, the link addresses of a linked list 34 for the six packet segments of a received packet are #4, 6, 8, 9, 13 and 14 in FIG. 1. And the six packet segments are stored on the shared memory 10 with its mapping block addresses 14 at &50, 70, 90, 100, 110 and 140 respectively. The final link address #14 will be linked to the link address #10 of the first packet segment of a next received packet. As a result, a flag 35 representing the link address #14 pointing to the link address #10 will be assigned. The assigning also indicate that the corresponding block of the link address #14 stores the last packet segment of the received packet. On the other hand, the link addresses #0, 7, 11, 12, 15, 3 and 5 of a linked list 36, illustrated by a broken line on the link RAM 30 in FIG.1, represents the released link address spaces of the previous packets been read. And to which the blank blocks &5, 15, 25, 35, 45, 55, and 65 in the free-buffer pool 12 on the shared memory 10 are respectively corresponded. These released link address spaces are available for link use of the packet segments of the next received packet. And the corresponding blank blocks are available for storage of the packet segments of the next received packet. In an unicast situation, a packet is transmitted to a designated output port. At this point, each packet segment of a packet is inserted to an appropriate output queue 37 according to its designated output port 40 with reference of the linked list 34 in order to achieve the object of transmitting the packet from the output port 40.
There are four steps to be sequentially carried out on the link RAM during the receiving to transmission of several packet segments of a packet. The first step is to get link. That is to assign the unused blocking data buffers of a shared memory to the plurality of packet segments and determine the corresponding link address spaces on the link RAM. The second step is to make link. That is to make the link addresses of the plurality of packet segments linked to form a linked list. The third step is to read link, which is to read the linked list. And the fourth step is to release link. That is to release the corresponding link address spaces after the linked list has been read. The following descriptions will further explain the process regarding to the receiving and transmission aspects, separately.
From aspect of the receiving, the packet segments of a packet firstly get link address spaces 31 that are available through an input port 20 and then the packet segments are written in. Then a linked list 34 is made and inserted to an output queue 37 to complete a receiving of the packet segments. FIG. 2 is a flow chart illustrating one example of the controlling process in receiving a packet according to the conventional Ethernet switching architecture described in FIG. 1. Listed below are the descriptions of the controlling steps with reference to FIG. 1.
Step 201: To get six link address spaces. That is, an input port 20 judges whether the number of link address spaces available for use on the link RAM 30 is less than six. Keep getting link address spaces while the number is less than six; otherwise go to Step 202.
Step 202: To judge whether there is a packet to be received by the input port. Yes then go to Step 203, otherwise go to End.
Step 203: To receive packet. Start writing the packet into the first block of the mapping blocks (e.g. the blocks &50, 70, 90, 100, 140, and 150 in FIG. 1) on the shared memory 10 of the obtained six link address spaces (e.g. #4, 6, 8, 9, 13, and 14 in FIG. 1).
Step 204: To write in packet data. That is to write in the packet data according to the current link addresses 33 (e.g. #4, 6, 8, 9, 13 and 14 on FIG. 1) and the link on the link RAM 30 of the packet segments 21 of the packet, and the mapping block addresses 14 on the shared memory 10.
Step 205: To judge whether a packet has been completed written. Yes then go to Step 208, otherwise go to Step 206.
Step 206: To judge whether a block has been completed written. Yes then go to Step 207, otherwise proceed the next address writing on the shared memory 10 and go back to Step 204.
Step 207: Proceed to linking, loop back to Step 204 and proceed to the next block writing. The proceeding to linking comprises: Assign only the next link address to the current link address and no further linking when the block just been written in is doing the first link. Assign the next link address to the current link address and link the current link address to the previous link address when the block just been written in is not doing a first link.
Step 208: To judge whether the packet is a good packet. Yes then go to Step 209; otherwise reject to receive the packet, release the link address spaces 31 on the link RAM 30 for a next packet to be received, and loop back to Step 202.
Step 209: To judge whether there are enough buffers on an output port 40. Yes then go to Step 210; otherwise abandon the received packet, release the link address spaces 31 on the link RAM 30 for a next packet to be received, and loop back to Step 202.
Step 210: To judge whether the packet is the first packet destined to the output port 40. Yes then proceed to Step 212, otherwise go to Step 211.
Step 211: To make link. That is to insert the current linked list of the packet to the tail address 43 of the output port 40 and to write in the flag 35 of the final link address of the packet on the link RAM 30.
Step 212: To write in the flag of the final link address of the packet on the link RAM 30 and to inform the output port 40 the starting link address of the packet on the link RAM 30.
From aspect of the transmission, the block addresses of the packet segments are first read, and then respectively read the packet segments in turn and its linked list to complete the transmission of the packet segments. In the final, the corresponding link address spaces been read over are released. FIG. 3 is a flow chart illustrating one example of the controlling process in transmitting a packet according to the conventional Ethernet switching architecture described in FIG. 1. Listed below are the descriptions of the processing steps with reference to FIG. 1:
Step 220: An output port 40 judges whether there is a packet for transmission. Yes then proceeds to Step 221, No go to ends.
Step 221: To read the header address on the output queue. That is to read the header address 38 on the output queue37 of the output port 40 to get the first block address. In the meantime, proceed to the Step 222 and Step 223.
Step 222: To read links. That is to read the link addresses of the linked list 34 of the packet sequentially and proceed to Step 224.
Step 223: To read in packet data. That is to read in the packet data according to the current link addresses 33 of the packet on the link RAM 30, and the mapping block addresses 14 on the shared memory 10. Then jump to Step 227.
Step 224: To judge whether the link of the last block has been read. Yes then proceed to Step 225, otherwise loop back to Step 222.
Step 225: To judge whether there exists a next packet for transmission. Yes then proceed to Step 226, otherwise jump to Step 227.
Step 226: To load the address of the last block. That is to load the link address of the last block of the packet segments of the transmitting packet and use it as the header address for the next packet for transmission. Proceed to Step 227.
Step 227: To judge whether the packet for transmission either been completely read or abortively transmit. Yes then proceed to Step 228, otherwise keep on judging.
Step 228: To release link. That is to sequentially release the link address spaces 31 corresponding to the packet segments that have been read on the output port. Proceed to Step 229.
Step 229: To judge whether the entire link address spaces 31 on the link RAM 30 have been released. Yes then loop back to Step 220, otherwise back to Step 228.
As shown in FIG. 2 and FIG. 3, the four steps of getting link, making link, reading link and releasing link which the linked list of the packet get through are co-managed by only a link RAM 30 during the receiving to the transmission process. Owing to this, the time required for each packet from the receiving to transmission is the product of the time required to get through the four steps (4×clock period), the block counts and the transmission port counts used. In the 10/100 MB/s Ethernet switching, the bandwidth required might not be limited by the linked list method described above. However, in high speed Ethernet switching, under the demand of the transmission time for a packet to be smaller than 672 ns (that is, the bandwidth is 1 Gb/s and above), the transmission port counts that is proportional to the transmitting time of the packet would be limited.
Accordingly, methods for solving bandwidth problems have been proposed. And one is to shorten the time required for transmitting packet by increasing the clock frequency of the system and thus increasing the bandwidth. However, this will cause the power consuming and poor reliability problems. Therefore, finding a method that can obtain multiple ports and high bandwidth without increasing clock speed beyond the permissible range for Ethernet switching is very desirable.